package com.cat.graphTheory;

import com.cat.binaryTree.Pair;

import java.util.*;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/number-of-ways-to-arrive-at-destination/?envType=problem-list-v2&envId=cNHS7dSX
 * @create 2025/9/25 15:37
 * @since JDK17
 */

public class Solution34 {
    static int N = ((int) (1e9 + 7));
    public int countPaths(int n, int[][] roads) {
        List<int[]>[] g = new List[n];
        Arrays.setAll(g, i -> new ArrayList<>());
        for (var e : roads) {
            g[e[0]].add(new int[] { e[1], e[2] });
            g[e[1]].add(new int[] { e[0], e[2] });
        }
        int[] ans = new int[n];
        long[] dis = new long[n];
        Arrays.fill(dis, Long.MAX_VALUE);
        PriorityQueue<Pair<Long, Integer>> heap = new PriorityQueue<>(Comparator.comparingLong(Pair::getKey));
        heap.add(new Pair<>(0L, 0));
        dis[0] = 0;
        ans[0] = 1;
        while (!heap.isEmpty()) { //
            var p = heap.poll();
            long c = p.getKey();
            int u = p.getValue();
            if (c > dis[u]) {
                continue;
            }
            if (u == n - 1) {
                return ans[u];
            }
            for (var x : g[u]) {
                long cost = c + x[1];
                if (cost == dis[x[0]]) {
                    ans[x[0]] = (ans[x[0]] + ans[u]) % N;
                } else if (cost < dis[x[0]]) {
                    dis[x[0]] = cost;
                    ans[x[0]] = ans[u];
                    heap.add(new Pair<>(cost, x[0]));
                }
            }
        }
        return ans[n - 1];
    }
}